package 其他.乘积小于K的子数组713;

public class Solution {
    /**
     * 计算乘积小于k的子数组数量
     * 通过维护一个滑动窗口，动态调整窗口的大小来解决问题
     *
     * @param nums 整数数组，其中子数组的乘积需要计算
     * @param k    乘积的上限值
     * @return 返回乘积小于k的子数组数量
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 如果k小于等于1，任何乘积都会大于等于1，直接返回0
        if (k <= 1) return 0;
        int n = nums.length;
        int left = 0; // 滑动窗口的左边界
        int ans = 0; // 记录满足条件的子数组数量
        int c = 1; // 当前窗口内元素的乘积，初始化为1（中性元素，乘以任何数等于原数）

        // 遍历数组，right是滑动窗口的右边界
        for (int right = 0; right < n; right++) {
            c *= nums[right]; // 将当前元素纳入乘积计算
            // 如果当前窗口的乘积大于等于k，需要移动左边界
            while (c >= k) {
                c /= nums[left]; // 从乘积中移除左边界元素
                left++; // 左边界向右移动
            }
            // 累加当前满足条件的子数组数量
            ans += right - left + 1;
        }

        // 返回满足条件的子数组总数
        return ans;
    }
}
